The paths more taken matching DOM trees to search logs for accurate webpage clustering.

Kronecker Graphs An Approach to Modeling Networks.

Mining broad latent query aspects from search sessions.
Search queries are typically very short, which means they are often underspecified or have senses that the user did not think of. A broad latent query aspect is a set of keywords that succinctly represents one particular sense, or one particular information need, that can aid users in reformulating such queries. We extract such broad latent aspects from query reformulations found in historical search session logs. We propose a framework under which the problem of extracting such broad latent aspects reduces to that of optimizing a formal objective function under constraints on the total number of aspects the system can store, and the number of aspects that can be shown in response to any given query. We present algorithms to find a good set of aspects, and also to pick the best k aspects matching any query. Empirical results on real-world search engine logs show significant gains over a strong baseline that uses single-keyword reformulations: a gain of 14 % and 23 % in terms of human-judged accuracy and click-through data respectively, and around 20 % in terms of consistency among aspects predicted for “similar ” queries. This demonstrates both the importance of broad query aspects, and the efficacy of our algorithms for extracting them.
ShatterPlots Fast Tools for Mining Large Graphs.

Quicklink selection for navigational query results.
Quicklinks for a website are navigational shortcuts displayed below the website homepage on a search results page, and that let the users directly jump to selected points inside the website. Since the real-estate on a search results page is constrained and valuable, picking the best set of quicklinks to maximize the benefits for a majority of the users becomes an important problem for search engines. Using user browsing trails obtained from browser toolbars, and a simple probabilistic model, we formulate the quicklink selection problem as a combinatorial optimizaton problem. We first demonstrate the hardness of the objective, and then propose an algorithm that is provably within a factor of (1 − 1/e) of the optimal. We also propose a different algorithm that works on trees and that can find the optimal solution; unlike the previous algorithm, this algorithm can incorporate natural constraints on the set of chosen quicklinks. The efficacy of our methods is demonstrated via empirical results on both a manually labeled set of websites and a set for which quicklink click-through rates for several webpages were obtained from a real-world search engine.
Generating succinct titles for web URLs.
How can a search engine automatically provide the best and most appropriate title for a result URL (link-title) so that users will be persuaded to click on the URL? We consider the problem of automatically generating link-titles for URLs and propose a general statistical framework for solving this problem. The framework is based on using information from a diverse collection of sources, each of which can be thought of as contributing one or more candidate link-titles for the URL. It can also incorporate the context in which the link-title will be used, along with constraints on its length. Our framework is applicable to several scenarios: obtaining succinct titles for displaying quicklinks, obtaining titles for URLs that lack a good title, constructing succinct sitemaps, etc. Extensive experiments show that our method is very effective, producing results that are at least 20 % better than non-trivial baselines.
Mortal Multi%2DArmed Bandits.
We formulate and study a new variant of the k-armed bandit problem, motivated by e-commerce applications. In our model, arms have (stochastic) lifetime after which they expire. In this setting an algorithm needs to continuously explore new arms, in contrast to the standard k-armed bandit model in which arms are available indefinitely and exploration is reduced once an optimal arm is identified with nearcertainty. The main motivation for our setting is online-advertising, where ads have limited lifetime due to, for example, the nature of their content and their campaign budgets. An algorithm needs to choose among a large collection of ads, more than can be fully explored within the typical ad lifetime. We present an optimal algorithm for the state-aware (deterministic reward function) case, and build on this technique to obtain an algorithm for the state-oblivious (stochastic reward function) case. Empirical studies on various reward distributions, including one derived from a real-world ad serving application, show that the proposed algorithms significantly outperform the standard multi-armed bandit approaches applied to these settings. 1
A graph%2Dtheoretic approach to webpage segmentation.
Categories and Subject Descriptors General Terms
Contextual advertising by combining relevance with click feedback.
Contextual advertising supports much of the Web’s ecosystem today. User experience and revenue (shared by the site publisher ad the ad network) depend on the relevance of the displayed ads to the page content. As with other document retrieval systems, relevance is provided by scoring the match between individual ads (documents) and the content of the page where the ads are shown (query). In this paper we show how this match can be improved significantly by augmenting the ad-page scoring function with extra parameters from a logistic regression model on the words in the pages and ads. A key property of the proposed model is that it can be mapped to standard cosine similarity matching and is suitable for efficient and scalable implementation over inverted indexes. The model parameter values are learnt from logs containing ad impressions and clicks, with shrinkage estimators being used to combat sparsity. To scale our computations to train on an extremely large training corpus consisting of several gigabytes of data, we parallelize our fitting algorithm in a Hadoop [10] framework. Experimental evaluation is provided showing improved click prediction over a holdout set of impression and click events from a large scale real-world ad placement engine. Our best model achieves a 25 % lift in precision relative to a traditional information retrieval model which is based on cosine similarity, for recalling 10 % of the clicks in our test data.
Epidemic thresholds in real networks.
How will a virus propagate in a real network? How long does it take to disinfect a network given particular values of infection rate and virus death rate? What is the single best node to immunize? Answering these questions is essential for devising network-wide strategies to counter viruses. In addition, viral propagation is very similar in principle to the spread of rumors, information, and “fads, ” implying that the solutions for viral propagation would also offer insights into these other problem settings. We answer these questions by developing a nonlinear dynamical system (NLDS) that accurately models viral propagation in any arbitrary network, including real and synthesized network graphs. We propose a general epidemic threshold condition for the NLDS system: we prove that the epidemic threshold for a network is exactly the inverse of the largest eigenvalue of its adjacency matrix. Finally, we show that below the epidemic threshold, infections die out at an exponential rate. Our epidemic threshold model subsumes many known thresholds for special-case graphs (e.g., Erdös–Rényi, BA powerlaw, homogeneous). We demonstrate the predictive power of our model with extensive experiments on real and synthesized graphs, and show that our threshold condition holds for arbitrary graphs. Finally, we show how to utilize our threshold condition for practical uses: It can dictate which nodes to immunize; it can assess the effects of a throttling
Multi%2Darmed bandit problems with dependent arms.
We provide a framework to exploit dependencies among arms in multi-armed bandit problems, when the dependencies are in the form of a generative model on clusters of arms. We find an optimal MDP-based policy for the discounted reward case, and also give an approximation of it with formal error guarantee. We discuss lower bounds on regret in the undiscounted reward scenario, and propose a general two-level bandit policy for it. We propose three different instantiations of our general policy and provide theoretical justifications of how the regret of the instantiated policies depend on the characteristics of the clusters. Finally, we empirically demonstrate the efficacy of our policies on large-scale realworld and synthetic data, and show that they significantly outperform classical policies designed for bandits with independent arms. 1.
Information Survival Threshold in Sensor and P2P Networks.
Abstract—Consider a network of, say, sensors, or P2P nodes, or bluetooth-enabled cell-phones, where nodes transmit information to each other and where links and nodes can go up or down. Consider also a ‘datum’, that is, a piece of information, like a report of an emergency condition in a sensor network, a national traditional song, or a mobile phone virus. How often should nodes transmit the datum to each other, so that the datum can survive (or, in the virus case, under what conditions will the virus die out)? Clearly, the link and node fault probabilities are important — what else is needed to ascertain the survivability of the datum? We propose and solve the problem using non-linear dynamical systems and fixed point stability theorems. We provide a closedform formula that, surprisingly, depends on only one additional parameter, the largest eigenvalue of the connectivity matrix. We illustrate the accuracy of our analysis on realistic and real settings, like mote sensor networks from Intel and MIT, as well as Gnutella and P2P networks. I.
Estimating rates of rare events at multiple resolutions.
We consider the problem of estimating occurrence rates of rare events for extremely sparse data, using pre-existing hierarchies to perform inference at multiple resolutions. In particular, we focus on the problem of estimating click rates for (webpage, advertisement) pairs (called impressions) where both the pages and the ads are classified into hierarchies that capture broad contextual information at different levels of granularity. Typically the click rates are low and the coverage of the hierarchies is sparse. To overcome these difficulties we devise a sampling method whereby we analyze a specially chosen sample of pages in the training set, and then estimate click rates using a two-stage model. The first stage imputes the number of (webpage, ad) pairs at all resolutions of the hierarchy to adjust for the sampling bias. The second stage estimates click rates at all resolutions after incorporating correlations among sibling nodes through a tree-structured Markov model. Both models are scalable and suited to large scale data mining applications. On a real-world dataset consisting of 1/2 billion impressions, we demonstrate that even with 95 % negative (non-clicked) events in the training set, our method can effectively discriminate extremely rare events in terms of their click propensity.
Bandits for Taxonomies A Model%2Dbased Approach.
We consider a novel problem of learning an optimal matching, in an online fashion, between two feature spaces that are organized as taxonomies. We formulate this as a multi-armed bandit problem where the arms of the bandit are dependent due to the structure induced by the taxonomies. We then propose a multi-stage hierarchical allocation scheme that improves the explore/exploit properties of the classical multiarmed bandit policies in this scenario. In particular, our scheme uses the taxonomy structure and performs shrinkage estimation in a Bayesian framework to exploit dependencies among the arms, thereby enhancing exploration without losing efficiency on short term exploitation. We prove that our scheme asymptotically converges to the optimal matching. We conduct extensive experiments on real data to illustrate the efficacy of our scheme in practice. 1
Page%2Dlevel template detection via isotonic smoothing.
We develop a novel framework for the page-level template detection problem. Our framework is built on two main ideas. The first is the automatic generation of training data for a classifier that, given a page, assigns a templateness score to every DOM node of the page. The second is the global smoothing of these per-node classifier scores by solving a regularized isotonic regression problem; the latter follows from a simple yet powerful abstraction of templateness on a page. Our extensive experiments on human-labeled test data show that our approach detects templates effectively.
Visualization of large networks with min%2Dcut plots%2C A%2Dplots and R%2DMAT.
What does a ‘normal ’ computer (or social) network look like? How can we spot ‘abnormal ’ sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”). The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such patterns and “laws”, including the “min-cut plots ” discovered by us. This is the first part of our NetMine package: given any large graph, it provides visual feedback about these patterns; any significant deviations from the expected patterns can thus be immediately flagged by the user as abnormalities in the graph. The second part of NetMine is the A-plots tool for visualizing the adjacency matrix of the graph in innovative new ways, again to find outliers. Third, NetMine contains the R-MAT (Recursive MATrix) graph generator, which can successfully model many of the patterns found in real-world graphs and quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. We present results on multiple, large real graphs, where we show the effectiveness of our approach.
Evolutionary clustering.

Graph mining Laws%2C generators%2C and algorithms.
How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: &#034;How can we generate synthetic but realistic graphs?&#034; To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.
Neighborhood Formation and Anomaly Detection in Bipartite Graphs.
Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (Neighborhood formation), and 2) finding abnormal nodes (Anomaly detection). And we propose algorithms to compute the neighborhood for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify abnormal nodes, using neighborhood information. We evaluate the quality of neighborhoods based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets. 1
Realistic
A vast body of theoretical research has focused either on overly simplistic models of parallel  computation, notably the PRAM, or overly specific models that have few representatives in  the real world. Both kinds of models encourage exploitation of formal loopholes, rather than  rewarding development of techniques that yield performance across a range of current and  future parallel machines. This paper offers a new parallel machine model, called LogP, that  reflects the critical technology trends underlying parallel computers. It is intended to serve  as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine  designers. Such a model must strike a balance between detail and simplicity in order to reveal  important bottlenecks without making analysis of interesting problems intractable. The model  is based on four parameters that specify abstractly the computing bandwidth, the communication  bandwidth, the communication delay, and the efficiency of coupling communication  and computation. Portable parallel algorithms typically adapt to the machine configuration, in  terms of these parameters. The utility of the model is demonstrated through examples that are  implemented on the CM-5.
Realistic
A vast body of theoretical research has focused either on overly simplistic models of parallel  computation, notably the PRAM, or overly specific models that have few representatives in  the real world. Both kinds of models encourage exploitation of formal loopholes, rather than  rewarding development of techniques that yield performance across a range of current and  future parallel machines. This paper offers a new parallel machine model, called LogP, that  reflects the critical technology trends underlying parallel computers. It is intended to serve  as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine  designers. Such a model must strike a balance between detail and simplicity in order to reveal  important bottlenecks without making analysis of interesting problems intractable. The model  is based on four parameters that specify abstractly the computing bandwidth, the communication  bandwidth, the communication delay, and the efficiency of coupling communication  and computation. Portable parallel algorithms typically adapt to the machine configuration, in  terms of these parameters. The utility of the model is demonstrated through examples that are  implemented on the CM-5.
Fully automatic cross%2Dassociations.
Large, sparse binary matrices arise in numerous data mining applications, such as the analysis of market baskets, web graphs, social networks, co-citations, as well as information retrieval, collaborative filtering, sparse matrix reordering, etc. Virtually all the popular methods for analysis of such matrices—e.g., k-means clustering, METIS graph partitioning, SVD/PCA and frequent itemset mining—require the user to specify various parameters, such as the number of clusters, number of principal components, number of partitions, and “support. ” Choosing suitable values for such parameters is a challenging problem. Cross-association is a joint decomposition of a binary matrix into disjoint row and column groups such that the rectangular intersections of groups are homogeneous. Starting from first principles, we furnish a clear, informationtheoretic criterion to choose a good cross-association as well as its parameters, namely, the number of row and column groups. We provide scalable algorithms to approach the optimal. Our algorithm is parameter-free, and requires no user intervention. In practice it scales linearly with the problem size, and is thus applicable to very large matrices. Finally, we present experiments on multiple synthetic and real-life datasets, where our method gives high-quality, intuitive results. ∗ This material is based upon work supported by the National
AutoPart Parameter%2DFree Graph Partitioning and Outlier Detection.
1 Introduction- Motivation Large, sparse graphs arise in many applications, under several guises. Conse-quently, because of their importance and prevalence, the problem of discovering structure in them has been widely studied in several domains, such as socialnetworks, co-citation networks, ecological food webs, protein interaction graphs and many others. Such structure can be used for getting insights into the graph,for example, for detecting &amp;quot;communities&amp;quot;. Problem Description: A graph G(V, E) has a set E of edges connecting anypair of nodes from a set
R%2DMAT A Recursive Model for Graph Mining.
How does a ‘normal ’ computer (or social) network look like? How can we spot ‘abnormal ’ sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”). The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such “laws ” and, more importantly, we propose a simple, parsimonious model, the “recursive matrix ” (R-MAT) model, which can quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. Contrary to existing generators, our model can trivially generate weighted, directed and bipartite graphs; it subsumes the celebrated Erdős-Rényi model as a special case; it can match the power law behaviors, as well as the deviations from them (like the “winner does not take it all ” model of Pennock et al. [20]). We present results on multiple, large real graphs, where we show that our parameter fitting algorithm (AutoMAT-fast) fits them very well. 1
A real%2Dtime expectation%2Dmaximization algorithm for acquiring multiplanar maps of indoor environments with mobile robots.


Epidemic Spreading in Real Networks An Eigenvalue Viewpoint.
Abstract How will a virus propagate in a real network?Does an epidemic threshold exist for a finite powerlaw graph, or any finite graph? How long does ittake to disinfect a network given particular values of infection rate and virus death rate? We answer the first question by providing equa-tions that accurately model virus propagation in any network including real and synthesized networkgraphs. We propose a general epidemic threshold condition that applies to arbitrary graphs: weprove that, under reasonable approximations, the epidemic threshold for a network is closely relatedto the largest eigenvalue of its adjacency matrix. Finally, for the last question, we show that infec-tions tend to zero exponentially below the epidemic threshold. We show that our epidemic threshold modelsubsumes many known thresholds for special-case graphs (e.g., Erd&amp;quot;os-R&#039;enyi, BA power-law, homoge-neous); we show that the threshold tends to zero for infinite power-law graphs. Finally, we illustrate thepredictive power of our model with extensive experiments on real and synthesized graphs. We show thatour threshold condition holds for arbitrary graphs.

Using EM to Learn 3D Models of Indoor Environments with Mobile Robots.
This paper describes an algorithm for generating compact 3D models of indoor environments with mobile robots. Our algorithm employs the expectation maximization algorithm to fit a lowcomplexity planar model to 3D data collected by range finders and a panoramic camera. The complexity of the model is determined during model fitting, by incrementally adding and removing surfaces. In a final post-processing step, measurements are converted into polygons and projected onto the surface model where possible. Empirical results obtained with a mobile robot illustrate that high-resolution models can be acquired in reasonable time. 1.
A Real%2Dtime Algorithm for Acquiring Multi%2DPlanar Volumetric Models with Mobile Robots.

